package com.zxy.leetcode._00000_00099._00040_00049;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * https://leetcode-cn.com/problems/permutations/
 *
 * 全排列
 * 给定一个 没有重复 数字的序列，返回其所有可能的全排列。
 *
 * 思路：回溯算法
 */
public class Test00046 {

    public static void main(String[] args) {
        Test00046 test = new Test00046();
        int[] nums = {1, 2, 3};
        System.out.println(test.permute(nums));
    }


    public List<List<Integer>> permute(int[] nums) {
        if (nums == null || nums.length == 0) {
            return Collections.emptyList();
        }

        List<List<Integer>> result = new ArrayList<>();
        backtrack(result, new ArrayList<>(), nums);

        return result;
    }


    private void backtrack(List<List<Integer>> result, List<Integer> selectNums, int[] allNums) {
        if (selectNums.size() == allNums.length) {
            result.add(new ArrayList<>(selectNums));
            return;
        }

        for (Integer num : allNums) {
            if (selectNums.contains(num)) {
                continue;
            }

            selectNums.add(num);
            backtrack(result, selectNums, allNums);
            selectNums.remove(num);
        }
    }


}
